package com.ls.que76_80;

/**
 * @author ：ls
 * @date ：2021/12/1 9:27
 * @description：...
 */
public class MinWindow {
    public static String minWindow(String s, String t) {
        if (s.length() < t.length())
            return "";
        int t_len = t.length();
        int s_len = s.length();
        int lw = 0, rw = 0;
        int lc=-1, rc=s_len;
        int[] freq = new int[58];   // 26 + 6 + 26
        int[] t_freq = new int[58];   // 26 + 6 + 26
        int i=0;
        for (i=0; i<t_len;i++) t_freq[t.charAt(i) - 'A'] += 1;
        while (lw <= s_len - t_len){
//            System.out.println(lw + " " + rw);
            if (rw - lw < t_len) {
                rw += 1;
                freq[s.charAt(rw - 1) - 'A'] += 1;
            }else if (rw - lw == t_len){
                // 检查是不是
                boolean flag = true;
                i=0;
                while (i < 58){
                    if (freq[i] < t_freq[i]){
                        flag = false;
                        break;
                    }
                    i+=1;
                }
                if (flag){
                    return s.substring(lw, rw);
                }else{
                    rw += 1;
                    if (rw > s_len) break;
                    freq[s.charAt(rw - 1) - 'A'] += 1;
                }


            }else {
                // 检查是不是
//                System.out.println("*** " + lw + " " + rw);
                boolean flag = true;
                i=0;
                while (i < 58){
                    if (freq[i] < t_freq[i]){
                        flag = false;
                        break;
                    }
                    i+=1;
                }
//                System.out.println(flag);
                if (flag){
                    if (rc - lc > rw - lw){
                        rc = rw;
                        lc = lw;
                    }
                    lw += 1;
                    freq[s.charAt(lw - 1) - 'A'] -= 1;
                }else{
                    if (rw == s_len)
                        break;
                    rw += 1;
                    freq[s.charAt(rw - 1) - 'A'] += 1;
                }


            }
        }
        if (lc == -1)
            return "";
        return s.substring(lc, rc);
    }

    public static void main(String[] args) {

        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }
}
